\appendix
\section{}

\begin{algorithm}[h]
\caption{Teste de Miller-Rabin com base dois ou não-resíduo pequeno}
\label{alg:mr2}

\begin{algorithmic}[1]
\REQUIRE Inteiro ímpar $n$.
\ENSURE Ou \textsc{composto} ou um inteiro $c$ tal que $(c/n) = -1$ e
$\epsilon \in R(n,c)$ com $\epsilon^4 = -1$ (i.e. $\Phi_8(\epsilon)=0$).

\IF{$n = 3$ (mod $4$)}
  \STATE $\alpha \gets 2^{\frac{n-3}{4}}$ (mod $n$)
  \STATE \textbf{if} $2\alpha^2 \neq \pm1$ (mod $n$) \textbf{then return}
  \textsc{composto}
  \STATE \textbf{else return} $c\gets -1$, $\epsilon \gets \alpha + \alpha x$
\ENDIF
\IF{$n = 5$ (mod $8$)}
  \STATE $\alpha \gets 2^{\frac{n-1}{4}}$ (mod $n$)
  \STATE \textbf{if} $\alpha^2 \neq -1$ (mod $n$) \textbf{then return}
  \textsc{composto}
  \STATE \textbf{else return} $c\gets 2$, $\epsilon \gets \frac{1+\alpha}{2} x$
\ENDIF
\IF{$n = 1$ (mod $8$)}
  \IF{$n$ é um quadrado perfeito} \RETURN \textsc{composto}
  \ELSE
    \STATE $c \gets$ valor aleatório pequeno tal que $(c/n) = -1$
    \STATE $\alpha \gets c^{\frac{n-1}{8}}$ (mod $n$)
    \STATE \textbf{if} $\alpha^4 \neq -1$ (mod $n$) \textbf{then return}
    \textsc{composto}
    \STATE \textbf{else return} $c$, $\epsilon \gets \alpha$
  \ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}





\begin{algorithm}[H]
\caption{Rodada do TFQS}
\label{alg:sqft}

\begin{algorithmic}[1]
\REQUIRE Inteiro ímpar $n$, inteiro pequeno $c$ tal que $(c,n)=-1$ e o
polinômio $\epsilon \in R(n,c)$ com $\epsilon^4 = -1$.
\ENSURE Ou \textsc{primo} ou \textsc{composto}

\STATE Escolha $z$ aleatório $\in R(n,c)$ com $(N(z)/n)=-1$
\IF{$z^n \neq \bar{z}$}
  \RETURN \textsc{composto}
\ENDIF
\IF{$z^{\frac{n^2-1}{8}} \not\in \{\pm\epsilon, \pm\epsilon^3\}$}
  \RETURN \textsc{composto}
\ENDIF
\RETURN \textsc{primo}
\end{algorithmic}
\end{algorithm}